﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

// 买卖股票的最佳时机3
class Solution
{
public:
    int maxProfit(vector<int>& prices)
    {
        const int INF = 0x3f3f3f3f;
        // f[i][j]:表示第i天结束之后，处于"买入"状态(手中有股票),完成j笔交易的最大利润
        // g[i][j]:表示第i天结束之后，处于"卖出"状态(手中没有股票),完成j笔交易的最大利润
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(3, -INF));
        auto g = f;
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j >= 1)
                    g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
            }
        }

        // 获得最大利润,可能完成了0,1,2笔交易
        int ret = 0;
        for (int i = 0; i < 3; i++)
        {
            ret = max(ret, g[n - 1][i]);
        }

        return ret;
    }
};

// 买卖股票的最佳时机4
class Solution
{
public:
    int maxProfit(int k, vector<int>& prices)
    {
        const int INF = 0x3f3f3f3f;
        // f[i][j]:表示第i天结束之后，处于"买入"状态(手中有股票),完成j笔交易的最大利润
        // g[i][j]:表示第i天结束之后，处于"卖出"状态(手中没有股票),完成j笔交易的最大利润
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(k + 1, -INF));
        auto g = f;
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < k + 1; j++)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j >= 1)
                    g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
            }
        }

        // 获得最大利润,可能完成了0,1,2，....k笔交易
        int ret = 0;
        for (int i = 0; i < k + 1; i++)
        {
            ret = max(ret, g[n - 1][i]);
        }

        return ret;
    }
};

//  单词拆分
class Solution
{
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        // d[i]:表示以i位置为结尾是否能够被拼接
        // j表示最后一个字符的起始位置0<=j<=i
        // 0到j-1 = dp[j-1]
        // 将wordDict放入哈希表中，提供查找子串的效率
        unordered_set<string> hash;
        for (auto& str : wordDict)
        {
            hash.insert(str);
        }
        int n = s.size();
        vector<bool> dp(n + 1);
        dp[0] = true;
        s = ' ' + s;
        for (int i = 1; i <= n; i++)
        {
            for (int j = i; j >= 1; j--)
            {
                if (dp[j - 1] && hash.count(s.substr(j, i - j + 1)))
                {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
};

// 环绕字符串中唯一的子字符串
class Solution
{
public:
    int findSubstringInWraproundString(string s)
    {
        // dp[i]:表示以i位置为结尾的所有子串在base中出现的次数
        int n = s.size();
        vector<int> dp(n, 1);
        for (int i = 1; i < n; i++)
        {
            // dp[i]分为长度为1，此时dp[i] = 1
            // dp[i]长度大于1，如果最后一个字符与前一个字符连续，则以前一个为结尾的和
            if (s[i] == s[i - 1] + 1 || (s[i] == 'a' && s[i - 1] == 'z'))
                dp[i] += dp[i - 1];
        }

        // 相同字符结尾的 dp 值，我们仅需保留「最⼤」的即可，其余 dp 值对应的⼦串都可以在最⼤的⾥⾯找到；
        int hash[26] = { 0 };
        for (int i = 0; i < n; i++)
        {
            hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
        }

        int sum = 0;
        for (auto& x : hash)
            sum += x;

        return sum;
    }
};
int main()
{
	return 0;
}